home *** CD-ROM | disk | FTP | other *** search
/ Java Primer Plus / Java Primer Plus (Waite Group Proess)(1996).iso / chapter17 / BinaryTree.java < prev    next >
Text File  |  1995-12-31  |  3KB  |  133 lines
  1. /*  Binary Tree Class */
  2.  
  3. import java.util.Stack;
  4.  
  5. class BinaryTree {
  6.  
  7.  BinaryTreeEntry root = new BinaryTreeEntry();
  8.  
  9.  /* empty constructor */
  10.  public BinaryTree() {}
  11.  
  12.  /* method to add a node to the Binary tree */
  13.  public void addnode(int k,Object someobject) throws
  14.                 DuplicateKeyException {
  15.   boolean leftright = true;
  16.   BinaryTreeEntry next,here=null;
  17.  
  18.   /* Is someone sending null objects? */
  19.   if (someobject == null) throw new NullPointerException();
  20.  
  21.   /* Check for Duplicates */
  22.   if (searchtree(k) != null)
  23.     throw new DuplicateKeyException("Key already exists in Structure");
  24.   System.out.println();
  25.   if (root.node == null) { root.node = someobject;
  26.                    root.key = k;
  27.                    return; 
  28.                      }
  29.   next = root;
  30.   while (next != null) {
  31.     here = next;
  32.     leftright = (k > here.key);
  33.     next = here.child[(leftright)?0:1];
  34.     }
  35.  
  36.   next = here.child[(leftright)?0:1] = new BinaryTreeEntry();
  37.   next.parent = here;
  38.   next.key = k;
  39.   next.node = someobject;
  40.    }
  41.  
  42.  
  43.  /* public method frontend search */
  44.  public Object searchfor(int k) {
  45.     BinaryTreeEntry temp = searchtree(k);
  46.     if (temp == null) return null;    
  47.     return temp.node;
  48.    }    
  49.  
  50.  
  51.  /* private tree search */
  52.  private BinaryTreeEntry searchtree(int k) {
  53.     boolean leftright = true;
  54.     BinaryTreeEntry columbus = root;
  55.  
  56.     while (columbus != null) {
  57.       if (columbus.key == k) return columbus;
  58.           leftright = (k > columbus.key);
  59.           columbus = columbus.child[(leftright)?0:1];
  60.       if (leftright) System.out.print("RIGHT ");
  61.        else System.out.print("LEFT ");
  62.     }
  63.     return null;
  64.     }
  65.  
  66. /* Deletes node with given key */
  67.  public void deleter(int k) {
  68.     int whichkid = 0;
  69.     BinaryTreeEntry temp;
  70.     BinaryTreeEntry exnode = searchtree(k);
  71.     if (exnode == null) return;
  72.  
  73.     BinaryTreeEntry exparent = exnode.parent;
  74.  
  75.     if (exparent != null)
  76.      whichkid = (exnode == exparent.child[0])?0:1;
  77.  
  78.     /* Easy cases */
  79.     for (int g=0;g<2;++g) {
  80.       if (exnode.child[g] == null) {
  81.         if (exnode.child[1-g] != null) 
  82.         exnode.child[1-g].parent = exparent;
  83.         if (exparent == null)  root = exnode.child[1-g];
  84.         else
  85.          exparent.child[whichkid] = exnode.child[1-g];
  86.         return;
  87.        }
  88.     }
  89.  
  90.     temp = exnode.child[1];
  91.  
  92.     while (temp.child[0] != null)
  93.       temp = temp.child[0];
  94.  
  95.      if (temp != exnode.child[1]) {
  96.       deleter(temp.key);
  97.       temp.child[1] = exnode.child[1];
  98.        }
  99.       temp.child[0] = exnode.child[0];
  100.      temp.parent   = exparent;
  101.       
  102.     
  103.      if (exparent == null) root = temp;
  104.      else
  105.      exparent.child[whichkid] = temp;
  106.   }
  107.  
  108.  
  109. /* methods to print out tree */
  110.  public void prtree() {
  111.     zip(root);
  112.     }
  113.  
  114.  public void zip(BinaryTreeEntry x) {
  115.  
  116.     if (x == null) return;
  117.     System.out.print(x.key + " --> " );
  118.     if (x.child[0] != null)
  119.      System.out.print(x.child[0].key + " " );
  120.     if (x.child[1] != null)
  121.      System.out.print(x.child[1].key);
  122.  
  123.         System.out.println();
  124.  
  125.     if (x.child[0] != null) zip(x.child[0]);
  126.     if (x.child[1] != null) zip(x.child[1]);
  127.     }
  128.  
  129.  
  130.  
  131.      
  132. }
  133.